package com.dataStructure.并查集;

//UnionFind
@SuppressWarnings("all")
public class 并查集_QuickFind extends 并查集{
    private int[] parents;

    public 并查集_QuickFind(int capacity) {
        super(capacity);
    }

    /**
     * 查找v所属的集合（根节点）
     * 传入的参数是parents数组的索引
     */
    public int find(int v) {
        rangCheck(v);
        //索引对应的元素即为根节点
        return parents[v];
    }

    /**
     * 合并两个集合
     */
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;

        //遍历数组里的所有元素，只要根节点是 p1 的，统统改成 p2。用这种方式来合并两个集合
        //将v1所在集合的所有元素都嫁接到v2是上
        for (int i = 0; i < parents.length; i++) {
            if (parents[i] == p1) {
                parents[i] = p2;
            }
        }
    }
}
